package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname LongestValidParentheses
 * @Description Leetcode 32. 最长有效括号 动态规划 难度 困难 只想对了一半 可以重做
 * @Date 2021/10/8 20:32
 * @Version 1.0
 */
public class LongestValidParentheses {


    /**
     * 动态规划思路
     *
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {

        int len = s.length();

        if (len == 1 || len == 0) {

            return 0;
        }

        int result = 0;
        //明确dp[]数组的含义，表示前i个字符串中所含有的
        int[] dp = new int[len + 1];
        dp[1] = 0;
        for (int i = 2; i <= len; i++) {

            if (s.charAt(i - 1) == ')') {
                if (s.charAt(i - 2) == '(') {
                    //场地为i的字符串含有的最长有效括号为
                    dp[i] = 2 + dp[i - 2];
                } else if (i - dp[i - 1] - 1 > 0 && s.charAt(i - 2 - dp[i - 1]) == '(') {
                    //
                    if (i - dp[i - 1] - 2 >= 0) {

                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;

                    } else {
                        dp[i] = dp[i - 1];
                    }
                }

            }

            result = Math.max(result, dp[i]);
//            System.out.println(result);
        }

        return result;
    }

    public static void main(String[] args) {
        LongestValidParentheses longestValidParentheses = new LongestValidParentheses();
        int i = longestValidParentheses.longestValidParentheses(")()())");
        System.out.println(i);

    }

}
